#include "transposition.h"

/* -------------------------- GLOBAL VARS ----------------------------------- */

int level = -1;
int Value[NMAX+1] = {0};
int keyscount = 0;
int lastTotal = 0;
int enies = 0;
char consonantes[] = {'S', 'R', 'N', 'D', 'L', 'C', 'T', 'M', 'P', 'B', 'G', 
'V', 'Y', 'Q', 'H', 'F', 'Z', 'J', 'X', 'W', 'K'};
char * paralabras2[] = { "QU", "DE", "LA", "EL", "EN", "SE", "UN", "NO", "SU", "AL"
, "ES" };
char * paralabras3[] = {"QUE", "LOS", "DEL", "LAS", "POR" };

void
decryptTransposition(char * message, char * rta)
{
	int len = 0, rows = 0;
	int n, found = FALSE;
	char * newtext, ** matrix, * text;
	FILE *fp;
	
	
	//fp = fopen(ANS_FILENAME, "w");
	//text = getMessage(argc, argv);
	//printf("%s\n", text);
	newtext = removeEnies(message);
	
	for (n=NMIN; n<=NMAX && found != TRUE; n++)
	{
		len = strlen(newtext);
		rows = round((double)len / n);
		matrix = createMatrix(newtext, n, rows);
		
		if(searchQuInMatrix(matrix, n, rows) > 0)
		{
			found = TRUE;
		}
	}
	
	if(n > NMAX && found != TRUE)
		printf("\nThe message can not be decyphered with any valid key of length" 
			   " between %d and %d\n\n", NMIN, NMAX);
	else
	{		
		//printf("\nThe message was encripted with a key of length %d\n\n", n-1);
		
		visit(0, matrix, n-1, rows, rta);
	}
	
	//fclose(fp);
	free(newtext);
}

/*
 char *
 rowCopy(char ** matrix, int cols, int rownum)
 {
 int i;	
 char * rta;
 
 if((rta = malloc(cols))== NULL)
 {
 fprintf(stderr, "Error: can't allocate memory\n");
 exit(1);
 }
 
 for(i = 0; i < cols; i++)
 rta[i] = matrix[rownum][i];
 
 return rta;
 }
 
 //busca si las letras que forman el string que se la pasa como primer argumento
 // se encuentran en la fila que se le indica de la matriz (no considera 
 // palabras que repiten las letras)
 char * 
 lettersInRow(char * string, char ** matrix, int cols, int rownum)
 {
 int i, j, len, found = 0;
 char * rta
 len = strlen(string);
 
 if((rta = malloc(len+1)) == NULL)
 {
 fprintf(stderr, "Error: can't allocate memory\n");
 exit(1);
 }
 
 for(i = 0; i < len; i++)
 {
 for(j = 0; j < cols && !found; j++)
 if(matrix[rownum][j] == string[i])
 found = j;
 
 if(!found)
 return NULL;
 else
 {
 rta[i] = found + '1';				
 found = 0;
 }
 }
 rta[i] = 0;
 
 return rta;
 }
 
 char *
 keyByAnagrams(char ** matrix, int cols, int rows)
 {
 int i, j, k, found = 0;
 char * aux, qLetter, uLetter;
 
 //Busco una columna que tenga una 'q' y una 'u'	
 for(i = 0; i < rows && !found; i++)
 for(j = 0; j < cols && !found; j++)
 {
 if(matrix[i][j] == 'q' || matrix[i][j] == 'Q' )
 {
 for(k = 0; k < cols && !found; k++)
 if(matrix[i][k] == 'u' || matrix[i][k] == 'U' )
 {
 found = i;
 qLetter = j;
 uLetter = k;
 }
 }
 }
 
 aux = rowCopy(matrix, cols, found);
 
 
 //Busco anagramas posibles de la columna obtenida
 // si ninguna fila tiene 'q' y 'u' elijo la primera de la matriz
 if(!found)
 {
 i = 1;
 
 }
 else
 i = found;
 
 
 }*/

int
searchQuInMatrix(char ** matrix, int cols, int rows)
{
	int i, j, k, l, found = 0, first = 1;
	
	for(i = 0; i < rows; i++)
		for(j = 0; j < cols; j++)
		{
			if(matrix[i][j] == 'Q' || matrix[i][j] == 'q')
			{			
				for(k = 0; k < 2 && !found; k++)
				{					
					for(l = 0; l < cols && !found; l++)
					{
						if(matrix[i+k][l] == 'U' || matrix[i+k][l] == 'u')
							found = 1;
					}
				}
				first = 1;
				if(!found)
					return -1;
				else
					found = 0;
			}
		}
	return 1;
}

static int
doStatistics(char * text, int len)
{
	int i, total = 0;
	
	for(i = 0; i < len; i++)
	{
		if(text[i] == 'Q' || text[i] == 'q') 
		{
			if(text[i+1] == 'U' || text[i+1] == 'u') 
			{
				total +=2;
				i++;
			}
			else
				return -1;
		}
		else
		{
			if((text[i] == 'E' || text[i] == 'e') &&
			   (text[i+1] == 'S' || text[i+1] == 's'))
			{
				total++;
				i++;
			}
			
			if((text[i] == 'D' || text[i] == 'd') &&
			   (text[i+1] == 'E' || text[i+1] == 'e'))
			{
				total++;
				i++;
			}
			
			if((text[i] == 'L' || text[i] == 'l') &&
			   (text[i+1] == 'A' || text[i+1] == 'a'))
			{
				total++;
				i++;
			}
			
			if((text[i] == 'E' || text[i] == 'e') &&
			   (text[i+1] == 'L' || text[i+1] == 'l'))
			{
				total++;
				i++;
			}
		}
	}
	
	return total;
}


//Transforma una matriz de caracteres a un string continuo de texto terminado en
// '\0'

static char *
matrixToText(char ** matrix, int cols, int rows)
{
	char * text;
	int i = 0, j = 0, k = 0;
	if((text = malloc(cols * rows + enies)) == NULL)
	{
		fprintf(stderr, "Error: can't allocate memory\n");
		exit(1);
	}
	
	for(i = 0, j = 0; j < rows; j++)
		for( k = 0; k < cols; k++, i++)
			text[i] = matrix[j][k];
	
	text[cols*rows+enies] = 0;
	return text;
}




char **
duplicateMatrix(char ** matrix, int cols, int rows)
{
	int i = 0, j = 0;
	char ** newmatrix;
	if((newmatrix = malloc(rows * sizeof(char *)))== NULL)
	{
		fprintf(stderr,"Error: can't allocate space\n");
		exit(1);
	}
	for(i = 0; i < rows; i++)
	{
		//se hace calloc por si el texto no es multiplo de la clave
		if((newmatrix[i] = calloc(cols, sizeof(char))) == NULL)
		{
			fprintf(stderr,"Error: can't allocate space\n");
			exit(1);
		}
	}
	
	for(i = 0; i < rows; i++)
		for(j = 0; j < cols; j++)
			newmatrix[i][j] = matrix[i][j];
	
	return newmatrix;
}

void
freeMatrix(char ** matrix, int cols, int rows)
{
	int i;
	
	for(i = 0; i < rows; i++)
		free(matrix[i]);
	
	free(matrix);
}
char *
intKeyToString(int * key, int len)
{
	char * ans;
	int i = 0, j = 0;
	if((ans = malloc(len + 1))== NULL)
	{
		fprintf(stderr,"Error: can't allocate space\n");
		exit(1);
	}
	
	for(i = 0, j = 0 ; j < len; i++, j++)
	{
		if(key[i] == 1 && i+1 < len && key[i+1] == 0)
		{		
			ans[j] = 'A';
			i++;
		}
		else
			ans[j] = key[i] + '0';
	}
	ans[j] = 0;
	return ans;
}

//Esta funcion recibe la una key y un archivo y la matriz a desencriptar y usando
//la key desencripta la matriz, y escribe el texto que da como resultado en el 
// archivo apuntado por fp
void
printKey(int * key, int len, char ** matrix, int cols, int rows, char * rta2)
{
	int newTotal = 0;
	char * rta, * anstext, ** newmatrix, * key2;
	
	keyscount++;
	
	key2 = intKeyToString(key, len);
	newmatrix = duplicateMatrix(matrix, cols, rows);
	transposeMatrix(newmatrix, key2, cols, rows);
	
	rta = matrixToText(newmatrix, cols, rows);
	rta[cols * rows] = 0;
	anstext = addEnies(rta);
	
	newTotal = doStatistics(anstext, cols * rows + enies);
	
	if(lastTotal <= newTotal)
	{
		//printf("KEY: %s\nTOTAL: %d\nTEXT:\n%s\n\n", key2, newTotal, anstext);
		printf("The used key was: \"%s\"\n\n", key2);
		strcpy(rta2, anstext);
		//fprintf(fp, "KEY: %s\nTOTAL: %d\nTEXT:\n%s\n\n", key2, newTotal, anstext);
		//printf("Your decyphered text has been written to a file named %s\n", ANS_FILENAME);
		lastTotal = newTotal;
	}
	
	free(key2);
	free(rta);
	free(newmatrix);
	free(anstext);
}
// Se utiliza para generar todas las claves de cierto largo (cols). Luego llama
// a printKey cuando tiene una clave posible 
//obtenida en parte de http://www.cut-the-knot.org/do_you_know/AllPerm.shtml
void 
visit(int k, char ** matrix, int cols, int rows, char * rta)
{
	int i;   
	level = level+1; 
	Value[k] = level;    
	
	if(level == cols)  
		printKey(Value, level, matrix, cols, rows, rta);
	else
		for (i = 0; i < cols; i++)
			if (Value[i] == 0)
				visit(i, matrix, cols, rows, rta);
	level = level-1; 
	Value[k] = 0;
}


void
printMatrix(char ** matrix, int cols, int rows)
{
	int i, j;	
	
	for(i = 0; i < rows; i++)
	{
		for(j = 0; j < cols; j++)
			printf("%c ", matrix[i][j]);
		
		printf("\n");
	}
}

//Crea la matriz correspondiente al texto enviado
static char **
createMatrix(char * text, int cols, int rows)
{
	int i = 0, j = 0;
	char ** matrix;
	
	if((matrix = malloc(rows * sizeof(char *)))== NULL)
	{
		fprintf(stderr,"Error: can't allocate space\n");
		exit(1);
	}
	for(i = 0; i < rows; i++)
	{
		//se hace calloc por si el texto no es multiplo de la clave para que 
		//relleno con 0
		if((matrix[i] = calloc(cols, sizeof(char))) == NULL)
		{
			fprintf(stderr,"Error: can't allocate space\n");
			exit(1);
		}
	}
	for(i = 0; i < rows; i++)
		for(j = 0; j < cols; j++)
			matrix[i][j] = text[i+j*rows];
	
	//printMatrix(matrix, cols, rows);
	return matrix;
}

static void
transposeMatrix(char ** matrix, char * key, int cols, int rows)
{
	int i = 0, j = 0, value = 0;
	char * aux;
	
	if((aux = malloc(cols + 1)) == NULL)
	{
		fprintf(stderr,"Error: can't allocate space\n");
		exit(1);
	}
	
	
	for(j = 0; j < rows; j++)
	{
		for(i = 0; i < cols; i++)
			aux[i] = matrix[j][i];
		aux[i] = 0;
		
		for(i = 0; i < cols; i++)
		{
			if(key[i] == 'A')
				value = 10;
			else
				value = key[i] - '1';
			
			matrix[j][i] = aux[value];
		};
	}
	return;
}

//Reemplaza la Ã± en un string por { y la mayuscula por }
static char *
removeEnies(char * text)
{
	char * rta;
	int i, j;
	
	if((rta = malloc(strlen(text) + 1)) == NULL) 
	{
		fprintf(stderr, "Error: can't allocate space");
		return NULL;
	}
	
	for(i = 0, j = 0;  text[j] != '\0'; j++, i++)
	{
		if( text[j] == -61 && text[j+1] == -79 )			
		{
			rta[i] = '{';
			j++;
			enies++;
		}
		else if( text[j] == -61 && text[j+1] == -111 )			
		{
			rta[i] = '}';
			j++;
			enies++;
		}
		else
			rta[i] = text[j];
	}
	//free(text);
	rta[i] = '\0';
	return rta;
}

static char *
addEnies(char * text)
{
	char * rta;
	int i, j;
	
	if((rta = malloc(strlen(text) + enies + 1)) == NULL) 
	{
		fprintf(stderr, "Error: can't allocate space");
		return NULL;
	}
	
	for(i = 0, j = 0;  text[j] != '\0'; j++, i++)
	{
		if( text[j] == '{') 			
		{
			rta[i++] = -61;
			rta[i] = -79;
		}
		else if( text[j] == '}')			
		{
			rta[i++] = -61;
			rta[i] = -111;
			//rta[i] = -47;
		}
		else
			rta[i] = text[j];
	}
	
	rta[i] = '\0';
	return rta;
}
